package test

// Trie TrieTree节点
type Trie struct {
	//标记当前节点是否为有效的路由
	//例如添加了路由/users
	//那么/user,/usr不能算作有效的路由
	//也就是只有字符"s"节点的IsPath字段为true
	IsPath bool
	//当前节点的子节点
	Children map[byte]*Trie
}

func New() Trie {
	return Trie{false, make(map[byte]*Trie)}
}

// Add 添加一个路由到TrieTree
func (t *Trie) Add(path string) {
	parent := t

	//逐个byte加入到TrieTree
	for i := range path {
		if child, ok := parent.Children[path[i]]; ok {
			//如果子节点不为空，继续向下遍历
			parent = child
		} else {
			//如果子节点为空，构造新的节点
			newChild := &Trie{false, make(map[byte]*Trie)}
			parent.Children[path[i]] = newChild
			parent = newChild
		}
	}
	//更新当前路由的叶子节点的IsPath字段
	parent.IsPath = true
}

// Find 返回指定路由是否存在于TrieTree中
func (t *Trie) Find(path string) bool {
	parent := t
	for i := range path {
		if child, ok := parent.Children[path[i]]; ok {
			parent = child
		} else {
			return false
		}

	}

	return parent.IsPath
}
